1924B - Space Harbour - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
set <int> hb;
ull c1[300010], c2[300010], c3[300010], val[300010];
int n, m, q;
void add(ull *c, int k, ull d)
{
   for(; k <= n; k += k & -k)
      c[k] += d;
}
ull ask(ull *c, int k)
{
   ull ans = 0;
   for(; k; k &= k-1)
   {
      ans += c[k];
   }
   return ans;
}
void chg0(int k, ull x)
{
   add(c1, k, x); add(c2, k, k*x); add(c3, k, k*x*k);
}
void chg1(int l, int r, ull v)
{
   chg0(l, v); if(r < n) chg0(r+1, -v);
}
void chg2(int l, int r, ull v)
{
   chg1(l+1, r, -v);
   chg1(l+1,l+1,1ll*v*(r-l));
}
ull query(int k)
{
   return (ask(c3,k)-(2*k+3)*ask(c2,k)+ask(c1,k)*(k+1)*(k+2))/2;
}
int id[300010];
int main()
{
   ios::sync_with_stdio(0);
   cin >> n >> m >> q;
   for(int i = 1; i <= m; ++i) cin >> id[i], hb.insert(id[i]);
   for(int i = 1; i <= m; ++i) cin >> val[id[i]];
   chg2(1, n, val[1]); sort(id+1, id+m+1);
   for(int i = 2; i < m; ++i)
   {
      chg2(id[i-1], n, -val[id[i-1]]);
      chg2(id[i-1], id[i], val[id[i-1]]);
      chg2(id[i], n, val[id[i]]);
   }
   while(q--)
   {
      int op, x, v; cin >> op >> x >> v;
      if(op == 1)
      {
         int L = *--hb.lower_bound(x), R = *hb.lower_bound(x);
         chg2(L, R, -val[L]);
         chg2(L, x, val[L]);
         chg2(x, R, val[x]=v); hb.insert(x);
      } else cout << (query(v)-query(x-1)) << '\n';
   }
   return 0;
}